// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-09 00:48
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DateTrain;

import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.HashMap;


public class BestRotation {
    /**
     * 获取给定数列中所有轮调可能得分最高的一种轮调
     * 得分按照大于不得分，小于等于得一份
     *
     * @param nums 给定数组
     * @return 返回轮调类型
     */
    public int bestRotation(int[] nums) {
        // 朴素解法 -> 列出所有轮调方法获取得分，返回得分最高的轮调方法
        // 使用HashMap实现对结果数据的存储 -> 长度为n的数组有n中轮调方法
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        // 用于存储结果数据 -> 轮调次数 + 实际得分
        HashMap<Integer, Integer> ans = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int situation = i;
            for (int j = 0; j < n; j++) {
                // n中轮调方法改为数字的对应的得分
                if (num <= ((situation) + n) % n) {
                    ans.put(j, ans.getOrDefault(j, 0) + 1);
                }
                situation--;
            }
        }
        return getMax(ans);
    }

    /**
     * 获取散列表中最大的value值
     *
     * @param ans 给定散列表
     * @return 返回最大值
     */
    private int getMax(HashMap<Integer, Integer> ans) {
        int maxKey = Integer.MIN_VALUE, maxValue = Integer.MIN_VALUE;
        for (Integer ints : ans.keySet()) {
            if (ans.get(ints) > maxValue) {
                maxKey = ints;
                maxValue = ans.get(ints);
            }
        }
        return maxKey;
    }


    public int bestRotationT(int[] nums) {
        int n = nums.length;
        int[] diffs = new int[n];
        for (int i = 0; i < n; i++) {
            int low = (i + 1) % n;
            int high = (i - nums[i] + n + 1) % n;
            diffs[low]++;
            diffs[high]--;
            if (low >= high) {
                diffs[0]++;
            }
        }
        int bestIndex = 0;
        int maxScore = 0;
        int score = 0;
        for (int i = 0; i < n; i++) {
            score += diffs[i];
            if (score > maxScore) {
                bestIndex = i;
                maxScore = score;
            }
        }
        return bestIndex;
    }


    @Test
    public void shout() {
        int[] test = {2, 3, 1, 4, 0};
        System.out.println(bestRotationT(test));
    }
}
